package com.zjsru.plan2023.oneday;

import java.util.Arrays;

/**
 * @Author: cookLee
 * @Date: 2023-08-29
 * 带因子的二叉树
 * \
 * 每个非叶结点的值应等于它的两个子结点的值的乘积。
 * \
 * 输入: arr = [2, 4]
 * 输出: 3
 * 解释: 可以得到这些二叉树: [2], [4], [4, 2, 2]
 * \
 * 输入: arr = [2, 4, 5, 10]
 * 输出: 7
 * 解释: 可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
 */
public class NumFactoredBinaryTrees {
    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        int len = arr.length;
        long[] dp = new long[len];
        long ans = 0;
        long mod = 1000000007;
        for (int i = 0; i < len; i++) {
            //作为单独一个节点的情况，初始化为 1
            dp[i] = 1;
            for (int left = 0, right = len - 1; left <= right; left++) {
                while (right >= left && (long) arr[i] < arr[left] * arr[right]) {
                    right--;
                }
                if (left <= right && (long) arr[i] == arr[left] * arr[right]) {
                    if (left == right) {
                        // //左右节点相等，说明有一个个非叶子节点
                        //dp[left] * dp[right] 表示左子树和右子树的组合数量，然后再加上 dp[i] 表示当前节点作为根节点的情况。
                        dp[i] = (dp[left] * dp[right] + dp[i]) % mod;
                    } else {
                        //左右节点不相等，说明有两个非叶子节点
                        dp[i] = (dp[left] * dp[right] * 2 + dp[i]) % mod;
                    }
                }
            }
            ans = (ans + dp[i]) % mod;
        }
        return (int) ans;
    }

    public static void main(String[] args) {
        NumFactoredBinaryTrees numFactoredBinaryTrees = new NumFactoredBinaryTrees();
        int[] arr = new int[]{2, 4};
        System.out.println(numFactoredBinaryTrees.numFactoredBinaryTrees(arr));
    }
}
